COCI/2010-2011/Contest #1 - 22.10.2010/ples/ples.ac.cpp

   1 // Andrés Mejía
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 const double EPS = 1e-9;
  29 int cmp(double x, double y = 0, double tol = EPS) {
  30     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  31 }
  32
  33 /*
  34 ACRush's Dinic algorithm for maximum flow
  35 Complexity: O(E V^2)
  36
  37 Usage:
  38 init(number of nodes, source, sink);
  39 Create graph using add_edge(int u, int v, int c1, int c2):
  40 This adds two directed edges: u -> v with capacity c1
  41 and v -> u with capacity c2.
  42 c2 by default is 0.
  43 After creating the graph, nedge contains the number of
  44 total edges.
  45 dinic_flow();
  46 This doesn't modify the capacity of the original graph,
  47 so you can run the algorithm several times on the same
  48 graph.
  49 If you want to run the algorithm with different sources/sinks
  50 assign the correct value to src and dest before calling
  51 dinic_flow().
  52 */
  53
  54 const int MAXN = 1001;
  55
  56 namespace Flow {
  57     const int maxnode=MAXN * 4 + 2;
  58     const int maxedge=2*(MAXN * (MAXN + 1) + 4 * MAXN);
  59     const int oo=1000000000;
  60
  61     int node,src,dest,nedge;
  62     int head[maxnode],point[maxedge],next[maxedge], flow[maxedge], work[maxnode], dist[maxnode];
  63     unsigned short capa[maxedge];
  64     short Q[maxnode];
  65
  66     void init(int _node,int _src,int _dest) {
  67         node=_node;
  68         src=_src;
  69         dest=_dest;
  70         for (int i=0;i<node;i++) head[i]=-1;
  71         nedge=0;
  72     }
  73
  74     void add_edge(int u,int v,int c1,int c2 = 0) {
  75         point[nedge]=v,capa[nedge]=c1,flow[nedge]=0,
  76             next[nedge]=head[u],head[u]=(nedge++);
  77
  78         point[nedge]=u,capa[nedge]=c2,flow[nedge]=0,
  79             next[nedge]=head[v],head[v]=(nedge++);
  80
  81     }
  82     bool dinic_bfs() {
  83         memset(dist,255,sizeof(dist));
  84         dist[src]=0;
  85         int sizeQ=0;
  86         Q[sizeQ++]=src;
  87         for (int cl=0; cl<sizeQ; cl++)
  88             for (int k=Q[cl],i=head[k]; i>=0; i=next[i])
  89         if (flow[i]<capa[i] && dist[point[i]]<0) {
  90             dist[point[i]]=dist[k]+1;
  91             Q[sizeQ++]=point[i];
  92         }
  93         return dist[dest]>=0;
  94     }
  95     int dinic_dfs(int x,int exp) {
  96         if (x==dest)return exp;
  97         for (int &i=work[x]; i>=0; i=next[i]) {
  98             int v=point[i],tmp;
  99             if (flow[i]<capa[i] && dist[v]==dist[x]+1 && (tmp=dinic_dfs(v,min(exp,capa[i]-flow[i])))>0) {
 100                 flow[i]+=tmp;
 101                 flow[i^1]-=tmp;
 102                 return tmp;
 103             }
 104         }
 105         return 0;
 106     }
 107     int dinic_flow() {
 108         for (int i=0; i<nedge; ++i) flow[i] = 0;
 109         int result=0;
 110         while (dinic_bfs()) {
 111             for (int i=0; i<node; i++) work[i]=head[i];
 112             while (1) {
 113                 int delta=dinic_dfs(src,oo);
 114                 if (delta==0) break;
 115                 result+=delta;
 116             }
 117         }
 118         return result;
 119     }
 120 }
 121
 122 /////////////// Maximum flow for sparse graphs ///////////////
 123 ///////////////    Complexity: O(V * E^2)      ///////////////
 124
 125 /*
 126 Usage:
 127 initialize_max_flow();
 128 Create graph using add_edge(u, v, c);
 129 max_flow(source, sink);
 130
 131 WARNING: The algorithm writes on the cap array. The capacity
 132 is not the same after having run the algorithm.  If you need
 133 to run the algorithm several times on the same graph, backup
 134 the cap array.
 135 */
 136
 137 // namespace Flow {
 138 // const int MAXE = 1.4 * (MAXN * (MAXN + 1) + 4 * MAXN); //Maximum number of edges
 139 // const int oo = INT_MAX / 4;
 140 // int cap[MAXE];
 141 // int first[MAXE];
 142 // int next[MAXE];
 143 // int adj[MAXE];
 144 // int current_edge;
 145 //
 146 // /*
 147 //   Builds a directed edge (u, v) with capacity c.
 148 //   Note that actually two edges are added, the edge
 149 //   and its complementary edge for the backflow.
 150 //  */
 151 // int add_edge(int u, int v, int c){
 152 //   adj[current_edge] = v;
 153 //   cap[current_edge] = c;
 154 //   next[current_edge] = first[u];
 155 //   first[u] = current_edge++;
 156 //
 157 //   adj[current_edge] = u;
 158 //   cap[current_edge] = 0;
 159 //   next[current_edge] = first[v];
 160 //   first[v] = current_edge++;
 161 // }
 162 //
 163 // void initialize_max_flow(){
 164 //   current_edge = 0;
 165 //   memset(next, -1, sizeof next);
 166 //   memset(first, -1, sizeof first);
 167 // }
 168 //
 169 // short q[MAXE];
 170 // int arrived_by[MAXE];
 171 // //arrived_by[i] = The last edge used to reach node i
 172 // int find_augmenting_path(int src, int snk){
 173 //   /*
 174 //     Make a BFS to find an augmenting path from the source to
 175 //     the sink.  Then pump flow through this path, and return
 176 //     the amount that was pumped.
 177 //   */
 178 //   memset(arrived_by, -1, sizeof arrived_by);
 179 //   int h = 0, t = 0;
 180 //   q[t++] = src;
 181 //   arrived_by[src] = -2;
 182 //   while (h < t && arrived_by[snk] == -1){ //BFS
 183 //     int u = q[h++];
 184 //     for (int e = first[u]; e != -1; e = next[e]){
 185 //       int v = adj[e];
 186 //       if (arrived_by[v] == -1 && cap[e] > 0){
 187 //         arrived_by[v] = e;
 188 //         q[t++] = v;
 189 //       }
 190 //     }
 191 //   }
 192 //
 193 //   if (arrived_by[snk] == -1) return 0;
 194 //
 195 //   int cur = snk;
 196 //   int neck = oo;
 197 //   while (cur != src) {
 198 //       neck = min(neck, cap[arrived_by[cur]]);
 199 //       cur = adj[arrived_by[cur] ^ 1];
 200 //   }
 201 //
 202 //   cur = snk;
 203 //   while (cur != src){
 204 //     //Remove capacity from the edge used to reach node "cur"
 205 //     //Add capacity to the backedge
 206 //     cap[arrived_by[cur]] -= neck;
 207 //     cap[arrived_by[cur] ^ 1] += neck;
 208 //     //move backwards in the path
 209 //     cur = adj[arrived_by[cur] ^ 1];
 210 //   }
 211 //   return neck;
 212 // }
 213 //
 214 // int max_flow(int src, int snk){
 215 //   int ans = 0, neck;
 216 //   while ((neck = find_augmenting_path(src, snk)) != 0){
 217 //     ans += neck;
 218 //   }
 219 //   return ans;
 220 // }
 221 // }
 222
 223 const int src = MAXN * 4, sink = src + 1;
 224
 225 int face(int number, bool isBoy) {
 226     int ans = isBoy ? 0 : 2 * MAXN;
 227     if (number < 0) ans += -number;
 228     else ans += number + MAXN;
 229     ans -= 1500;
 230     //printf("number = %d, isBoy = %d, ans = %d\n", number, isBoy, ans);
 231     assert(ans < 4 * MAXN);
 232     return ans;
 233 }
 234
 235 unsigned short cnt[4 * MAXN];
 236
 237 int main(){
 238     //D(Flow::maxedge);
 239     int n;
 240     scanf("%d", &n);
 241     for (int i = 0; i < n; ++i) {
 242         int x; scanf("%d", &x);
 243         assert(1500 <= abs(x) and abs(x) <= 2500);
 244         int k = face(x, true);
 245         cnt[k]++;
 246         //printf("cnt[boy = %d] = %d\n", x, cnt[k]);
 247     }
 248     for (int i = 0; i < n; ++i) {
 249         int x; scanf("%d", &x);
 250         assert(1500 <= abs(x) and abs(x) <= 2500);
 251         int k = face(x, false);
 252         cnt[k]++;
 253         //printf("cnt[girl = %d] = %d\n", x, cnt[k]);
 254     }
 255
 256     Flow::init(Flow::maxnode, src, sink);
 257     //Flow::initialize_max_flow();
 258
 259     for (int boy = -2500; boy <= -1500; ++boy) {
 260         if (cnt[face(boy, true)] == 0) continue;
 261         for (int girl = 1500; girl < -boy; ++girl) {
 262             if (cnt[face(girl, false)] == 0) continue;
 263             Flow::add_edge(face(boy, true), face(girl, false), Flow::oo);
 264             //printf("Added edge from boy = %d to girl = %d\n", boy, girl);
 265         }
 266     }
 267
 268     for (int boy = 1500; boy <= 2500; ++boy) {
 269         if (cnt[face(boy, true)] == 0) continue;
 270         for (int girl = -boy-1; girl >= -2500; --girl) {
 271             if (cnt[face(girl, false)] == 0) continue;
 272             Flow::add_edge(face(boy, true), face(girl, false), Flow::oo);
 273             //printf("Added edge from boy = %d to girl = %d\n", boy, girl);
 274         }
 275     }
 276
 277     for (int k = 1500; k <= 2500; ++k) {
 278         if (cnt[face(k, true)] > 0) {
 279             Flow::add_edge(src, face(k, true), cnt[face(k, true)]);
 280         }
 281         if (cnt[face(-k, true)] > 0) {
 282             Flow::add_edge(src, face(-k, true), cnt[face(-k, true)]);
 283         }
 284
 285         if (cnt[face(k, false)] > 0) {
 286             Flow::add_edge(face(k, false), sink, cnt[face(k, false)]);
 287         }
 288
 289         if (cnt[face(-k, false)] > 0) {
 290             Flow::add_edge(face(-k, false), sink, cnt[face(-k, false)]);
 291         }
 292     }
 293
 294     int ans = Flow::dinic_flow();
 295     //int ans = Flow::max_flow(src, sink);
 296     cout << ans << endl;
 297     return 0;
 298 }